#
# Copyright (C) 2011: Gabriel Tremblay (initnull@gmail.com)
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software Foundation,
# Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
#
__author__ = 'Gabriel Tremblay'

import codecs
import itertools
import math


# Apply a list of conversions to a wordList, lowercase the word, remove whitespace and \n
# The conversions must be in the format of <orinalchar>=<replacement> ex: i=e
# This can be used to replace accents and special chars
def cleanUpAndNormalizeWordList(wordlist, conversions):
    cleanList = list()
    for word in wordlist:
        for conversion in conversions:
            # Get string to replace and replacement
            tokens = conversion.split("=")
            # remove EOL from replacement token
            tokens[1] = tokens[1].replace("\n", "")
            # Replace
            word = unicode(word.replace(tokens[0], tokens[1]))

        # remove empty spaces
        word = word.strip()
        # Lowercase
        word = word.lower()
        # remove \n
        word = word.replace("\n", "")
        # Add the converted word to the clean list
        cleanList.append(word)

    # Sort list
    cleanList.sort()

    return cleanList


# entry point
if __name__ == "__main__":
    dictionary = "dico.txt"
    conversion = "conversion-noacc.txt"
    wordBase = "Stations.txt"
    output = "output.txt"
    # Add an empty space after each expression (or unique word) to add more anagrams
    addEmptySpaceAtEndOfExpressions = True


    # Convert characters in wordlist and add to an array
    dictionaryFile = codecs.open(dictionary, encoding='utf-8')

    # open conversion file as unicode utf-8
    conversionFile = codecs.open(conversion, encoding='utf-8')

    # Read file in memory (Circumvent a weird bug in python 2.6)
    tempDictionaryList = dictionaryFile.readlines()
    tempConversionList = conversionFile.readlines()

    output = codecs.open(output, mode="w",  encoding='utf-8')

    print "Loading and filtering wordlist"
    dictionaryList = cleanUpAndNormalizeWordList(tempDictionaryList, tempConversionList)

    # Create a Hashed dictionary for fast seek
    wordDic = dict([(x, x) for x in dictionaryList])
    print "WordList Ready (%d words loaded)" %len(wordDic)

    # Load words to anagram
    print "Opening and sorting sentences to anagram"
    targetListFile = codecs.open(wordBase, encoding='utf-8')
    tmpTargetList = targetListFile.readlines()

     # Store the final wordlist here
    targetList = cleanUpAndNormalizeWordList(tmpTargetList, tempConversionList)
    print "Anagram target ready (%d targets)" %len(targetList)

    # Find anagrams
    # 1- Find all character permutations including the space char
    # 2- Split each words on Space " " to create separate words
    # 3- For each word in a word set, validate that each word exist, if yes, we have an anagram
    for stationName in targetList:
        output.write("\nSource word: %s\n" %stationName)

        for word in stationName.split(" "):
            print "Getting Permutation for word: %s" %word

            # Add an empty space to each word to create more creative anagrams (acadie" ") = ca aide
            if addEmptySpaceAtEndOfExpressions:
                word += ' '

            possiblePermutations = math.factorial(len(word))
            print "%d permutations possible" %possiblePermutations

            # Looks for anagram and store them in a temp set (remove duplicates)
            anagrams = set()

            for permutationTuple in itertools.permutations(word, len(word)):
                # Create a word out of letter tuple
                currentWord = "".join(permutationTuple).strip()

                # Split the permutation on " " to make separate words
                splittedWord = list(currentWord.split(" "))

                # We don't use set.intersection since it's too slow for this application.
                # 1 match is perfect.
                foundAnagram = True
                for uniqueWord in splittedWord:
                    if wordDic.get(uniqueWord) is None:
                        foundAnagram = False
                        break

                if foundAnagram:
                    anagrams.add(currentWord)


            # Save anagrams
            if len(anagrams) > 0:
                print "%d Anagrams found!" %len(anagrams)
                sortedAnagrams = list(anagrams)
                sortedAnagrams.sort()

                for item in sortedAnagrams:
                    output.write("\t%s " %item)
                    output.write("\n")

            print "Anagram search for %s done.\n" %stationName

    print "Anagram search ended."
